package algorithm.sort.review3;

import java.util.Arrays;

public class Merge {
    public static void main(String[] args) {
        int[] arr = {3, 3, 4, 1, 3, 56, 242, 1};
        int[] tmp = new int[arr.length];
        sort(arr, 0, arr.length - 1, tmp);

        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int[] arr,int left, int right, int[] tmp){
        if (left >= right) return;
        int mid = (left + right) / 2;
        sort(arr,left,mid,tmp);
        sort(arr,mid + 1,right,tmp);
        merge(arr,left,mid,right,tmp);
    }
    public static void merge(int[] arr, int left, int mid, int right, int[] tmp){
        int k = 0;
        int j = mid+1;
        int i = left;
        while (i <= mid && j <= right){
            if (arr[i] < arr[j]){
                tmp[k++] = arr[i++];
            }else{
                tmp[k++] = arr[j++];
            }
        }
        while (i <= left){
            tmp[k++] = arr[i++];
        }
        while (j <= right){
            tmp[k++] = arr[j++];
        }
        //copy
        k = 0;
        while (left <= right){
            arr[left++] = tmp[k++];
        }
    }
}
